/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-05 15:23:58
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-06 20:41:39
 * @FilePath: \LeetCode\90.子集-ii.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=90 lang=cpp
 *
 * [90] 子集 II
 *
 * 方法1：根据子集树进行搜索
 * - 重复元素当作一个集合，要么不选，要么逐个累加选择
 *
 * 方法2（官方题解）：在78位运算操作的基础上
 * - 判断重复元素：只选择第一个
 * - 对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中
 */

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

// /* 方法1：*/
// std::unordered_map<int, int> numHash;
// std::vector<std::pair<int, int>> numPair;
// std::vector<std::vector<int>> result;
// std::vector<int> n;
// int len;

// void visitSubTree(int k)
// {
//     if (k == len)
//     {
//         result.push_back(n);
//         return;
//     }
//     /* 左子树 */
//     for (int i = 0; i < numPair[k].second; i++)
//     {
//         n.push_back(numPair[k].first);
//         visitSubTree(k + 1);
//     }
//     /* 右子树 */
//     for (int i = 0; i < numPair[k].second; i++)
//         n.pop_back();
//     visitSubTree(k + 1);
// }

// @lc code=start
class Solution
{
private:
    std::vector<std::vector<int>> result;
    std::vector<int> v_selected;

public:
    std::vector<std::vector<int>> subsetsWithDup(std::vector<int> &nums)
    {
        std::sort(nums.begin(), nums.end()); // 集中重复元素

        int len = nums.size();
        bool overselect = false;                           // 判断是否有重复选择
        for (uint32_t mask = 0; mask < (1 << len); mask++) // 2^len
        {
            v_selected.clear();
            overselect = false;

            for (int i = 0; i < len; i++)
            {
                if (mask & (1 << i))
                {
                    v_selected.emplace_back(nums[i]);
                    /* 重复元素 & 前者未被选择 */
                    if (i > 0 && nums[i] == nums[i - 1] &&
                        ((mask >> (i - 1)) & 1) == 0) // i-1 未被选择
                    {
                        overselect = true;
                        break;
                    }
                }
            }

            if (!overselect)
                result.emplace_back(v_selected);
        }

        return result;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {1, 2, 2, 3, 2, 3};

    std::vector<std::vector<int>> result = solution.subsetsWithDup(nums);
    for (auto v : result)
    {
        for (auto n : v)
            std::cout << n << " ";
        std::cout << std::endl;
    }

    return 0;
}